package com.yangli.leecode.mashib.interview;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @Description
 * @Author liyang
 * @Date 2023/2/2 15:08
 */
public class Four {
    public static void main(String[] args){

        Four four = new Four();
        System.out.println(four.findTarget(new int[][]{{1, 3}, {1, 2}, {4, 3}, {5, 3}, {4, 3}, {5, 3}}));

        System.out.println(four.findTarget3(new int[][]{{1, 3}, {1, 2}, {4, 3}, {5, 3}, {4, 3}, {5, 3}}));

    }


    //暴力递归
    public int findTarget(int[][] arr){
        if ((arr == null || arr.length < 2 || (arr.length & 1) != 0)) {
            return 0;
        }

        return process(arr, 0, 0, 0, 0);
    }

    public int process(int[][] arr, int index, int alimit, int blimit, int sum){//==>如何精简参数
        if (index == arr.length) {
            return sum;
        }
        if (alimit == arr.length / 2) {
            return process(arr, index + 1, alimit, blimit + 1, arr[index][1] + sum);
        }
        if (blimit == arr.length / 2) {
            return process(arr, index + 1, alimit + 1, blimit, arr[index][0] + sum);
        }
        return Math.max(process(arr, index + 1, alimit + 1, blimit, arr[index][0] + sum), process(arr, index + 1, alimit, blimit + 1, arr[index][1] + sum));
    }

    public int findTarget2(int[][] arr){
        if ((arr == null || arr.length < 2 || (arr.length & 1) != 0)) {
            return 0;
        }

        return process2(arr, 0, arr.length >> 1);
    }

    //rest表示A区域的名额，去A还可以有多少个司机
    public int process2(int[][] arr, int index, int alimit){//==>如何精简参数
        if (index == arr.length) {
            return 0;
        }
        if (alimit == 0) {
            return arr[index][1] + process2(arr, index + 1, alimit);//arr[index][1]用这个替代 arr[index][1]+sum
        }
        if (arr.length-index == alimit) { //表示只能去A
            return arr[index][0] + process2(arr, index + 1, alimit + 1);
        }
        return Math.max(arr[index][1] + process2(arr, index + 1, alimit), arr[index][0] + process2(arr, index + 1, alimit + 1));
    }

    public int findTarget3(int[][] arr){
        if ((arr == null || arr.length < 2 || (arr.length & 1) != 0)) {
            return 0;
        }
        int m = arr.length >> 1;
        int[][] dp = new int[arr.length + 1][m + 1];
        for (int index = arr.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= m; rest++) {
                if (rest == 0) {
                    dp[index][rest] = arr[index][1] + dp[index + 1][rest];
                    continue;
                }
                if (index == rest) {
                    dp[index][rest] = arr[index][0] + dp[index + 1][rest - 1];
                    continue;
                }
                dp[index][rest] = Math.max(arr[index][0] + dp[index + 1][rest - 1], arr[index][1] + dp[index + 1][rest]);
            }
        }
        return dp[0][m];
    }


    public int findTargetN(int[][] arr){
        if (arr.length == 0) {
            return 0;
        }
        Map<Integer, Integer> indexMap = new LinkedHashMap<>();
        for (int i = 0; i < arr.length; i++) {
            indexMap.put(i, arr[i][0] - arr[i][1]);
        }
        indexMap.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEachOrdered(entry -> {
            indexMap.put(entry.getKey(), entry.getValue());
        });
        int i = 0;
        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : indexMap.entrySet()) {
            if (i < arr.length / 2) {
                sum += arr[entry.getKey()][1];
            } else {
                sum += arr[entry.getKey()][0];
            }
            i++;
        }
        return sum;
    }

}
